public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
        // 暴力循环
        /*
        int res = 0;

        for (int i = 0; i <= n; i++) {
            for (int j = i; j > 0; j /= 10) {
                if (j % 10 == 1) {
                    res++;
                }
            }
        }

        return res;
        */

        // 数学公式
        int res = 0;
        int mulBase = 1;
        for (int i = 0; mulBase <= n; i++) {
            res += (n / (mulBase * 10)) * mulBase;

            // 余数
            if (n % (mulBase * 10) >= 2 * mulBase) {
                res += mulBase;
            }
            else if (n % (mulBase * 10) >= mulBase) {
                res += n % (mulBase * 10) - mulBase + 1;
            }

            mulBase *= 10;
        }

        return res;
    }
}


/*
 1-9: 1
 10-19: 11
 20-29: 1
 ...
 100-109: 1 + 10
 110-119: 11 + 10
 120-129: 1 + 10
 ...
 200-210: 10
 */  